1. Technical Field of the Invention
Various embodiments of the present disclosure relate to processors and, more particularly, to a method and system of control flow graph construction through integrated hardware resources and software.
2. Background Information
Java™ is a programming language that, at the source code level, is similar to object oriented programming languages such as C++. Java™ language source code is compiled into an intermediate representation based on a plurality “bytecodes” that define specific tasks. In some implementations, the bytecodes are further compiled to machine language for a particular processor. In order to speed the execution of Java™ language programs, some processors are specifically designed to execute some of the Java™ bytecodes directly. Many times, a processor that directly executes Java™ bytecodes is paired with a general purpose processor so as to accelerate Java™ program execution in a general or special purpose machine. Acceleration may also be achieved by optimization of the executable code by way of a compiler.
A control flow graph (CFG) is a data structure used internally by compilers to abstractly represent a procedure or program. Each node in a control flow graph represents a basic block which is a straight-line piece of code with no jumps or jump targets. Edges are used to represent jumps in the control flow. A CFG has an entry block, through which control enters the CFG, and an exit block, through which all control flow leaves. A CFG may be used in the optimization of executable code generated by compilers. For example, a CFG allows a compiler to detect non-syntactical loops and dead code.
FIG. 1A shows an example set of instructions 10. The set of instructions 10 may comprise Java™ opcodes or instructions (including virtual instructions) of any programming language supported by the Java State Machine based on byte. The set of instructions 10 contains one or more leader instructions, indicated in FIG. 1A as references 12, 14, 16, 18, 20, 22, 24, 26, and 28 respectively. A leader instruction is an instruction that starts a basic block in the CFG. A leader instruction may change the flow of control, for example, by starting a catch block; there are, however, instructions that change the control flow and are not leader instructions. Instructions targeted by a conditional branch are leader instructions as well. FIG. 1B illustrates one embodiment of a CFG being an abstract representation of the set of instructions 10. In the CFG, each leader instruction begins a basic block. For instance, in the example illustrated by FIGS. 1A and 1B, the first instruction 12 starts the basic block 30. Instruction 14 starts the basic block 32, instruction 16 starts block 34, and instruction 18 starts block 36. Similarly, instruction 20 starts block 38, instruction 22 starts 40, instruction 24 starts block 42, instruction 26 starts block 44, and instruction 28 starts block 46. The edges connecting the blocks in FIG. 1B represent the control flow from each basic block to other blocks.
A purely software approach to CFG construction has been taken in the related art. Specifically, CFG construction has been done employing the Java Virtual Machine (“JVM”) for Java programs. In such an approach, CFG construction may be realized in at least two passes, one to identify leader instructions that start a block in the CFG, and then one or more to create the CFG. The loop that scans the program in a linear fashion to build the CFG increases execution time, unnecessarily ties up processing resources, and consumes power. In the case of an Ahead-in-Time compiler, CFG construction increases the application startup time, while in the case of a Dynamic Adaptive compiler, CFG construction increases the application execution time. Thus, construction of the CFG, while necessary to design and execution of a compiler, introduces undesirable delay.
Thus, there is a need for an efficient approach of integrating hardware and software for CFG construction in object-oriented programming, such as Java.